package com.atcumt.lcSolution;

import java.util.*;

// 滑动窗口
public class LC7 {

    /**
     * 串联所有单词的子串
     * <p>
     * 输入：s = "barfoothefoobarman", words = ["foo","bar"]
     * 输出：[0,9]
     */
    public List<Integer> findSubstring(String s, String[] words) {

        return null;
    }

    /**
     * 最长特殊序列
     * <p>
     * 输入: strs = ["aba","cdc","eae"]
     * 输出: 3
     * <p>
     * 最长特殊子序列 = 最长子序列(就是其本身)+该序列不能是其他序列的子序列
     */
    public int findLUSlength(String[] strs) {
        Map<String, Integer> map = new HashMap<>();
        int max = 0;
        for (String s : strs) {
            map.put(s, map.getOrDefault(s, 0) + 1);
        }

        HashSet<String> set1 = new HashSet<>(); // 存放重复字符串
        HashSet<String> set2 = new HashSet<>(); // 存放不重复字符串

        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            String key = entry.getKey();
            if (entry.getValue() > 1) {
                set1.add(key);
            } else {
                set2.add(key);
            }
        }

        for (String s2 : set2) {
            int cur = s2.length();
            for (String s1 : set1) {
                if (isSubsequence(s2, s1)) {
                    cur = 0;
                    break;
                }
            }
            max = Math.max(cur, max);
        }
        return max == 0 ? -1 : max;
    }

    // 判断是否为子序列
    private boolean isSubsequence(String s2, String s1) {
        int index2 = 0, index1 = 0;
        while (index2 < s2.length() && index1 < s1.length()) {
            if (s2.charAt(index2) == s1.charAt(index1)) {
                index2++;
            }
            index1++;
        }
        return index2 == s2.length();
    }

    /**
     * 无重复字符的最长子串
     */
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) {
            return 0;
        }
        int max = 0;
        int left = 0;
        Map<Character, Integer> map = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {
                left = Math.max(left, map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i), i);
            max = Math.max(max, i - left + 1);
        }
        return max;
    }
}
